#include <stdio.h>
#include <limits.h>

#define V 4  // 顶点数
#define INF 99999

// 函数用于打印解决方案
void printSolution(int dist[][V], char vertices[]) {
    printf("The following matrix shows the shortest distances between every pair of vertices:\n");
    printf("    ");
    for (int i = 0; i < V; i++) {
        printf("%4c", vertices[i]);
    }
    printf("\n");
    for (int i = 0; i < V; i++) {
        printf("%c  ", vertices[i]);
        for (int j = 0; j < V; j++) {
            if (dist[i][j] == INF)
                printf("%4s", "INF");
            else
                printf("%4d", dist[i][j]);
        }
        printf("\n");
    }
}

// 实现 Floyd Warshall 算法
void floydWarshall(int graph[][V], char vertices[]) {
    int dist[V][V], i, j, k;

    // 初始化距离矩阵
    for (i = 0; i < V; i++)
        for (j = 0; j < V; j++)
            dist[i][j] = graph[i][j];

    // 添加所有顶点作为中间顶点
    for (k = 0; k < V; k++) {
        // 选择所有顶点作为源点
        for (i = 0; i < V; i++) {
            // 选择所有顶点作为目的地
            for (j = 0; j < V; j++) {
                // 如果顶点 k 是从 i 到 j 的最短路径的中间顶点
                // 更新 dist[i][j]
                if (dist[i][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }

    // 打印最终结果
    printSolution(dist, vertices);
}

int main() {
    // 使用字符型数组定义顶点
    char vertices[V] = {'A', 'B', 'C', 'D'};

    // 邻接矩阵表示的图
    int graph[V][V] = {{0,   5,  INF, 10},
                       {INF, 0,   3, INF},
                       {INF, INF, 0,   1},
                       {INF, INF, INF, 0}};

    // 执行 Floyd-Warshall 算法
    floydWarshall(graph, vertices);
    return 0;
}
